package com.atcumt.Carl.Dfs;

import java.util.ArrayList;
import java.util.List;

public class Dfs03 {

    /**
     * N皇后
     * 方法：棋盘问题，只回溯行，从上往下放置
     */
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {

        char[][] board = new char[n][n]; // 初始化棋盘
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        NQueensHelper(n, board, 0);
        return res;
    }

    private void NQueensHelper(int n, char[][] board, int row) {
        if (row == n) {
            res.add(charToList(board)); // 将 char数组转化为list集合
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(board, row, col, n)) {
                continue; // 剪枝
            }
            board[row][col] = 'Q';
            NQueensHelper(n, board, row + 1);
            board[row][col] = '.';
        }
    }

    // 排除三种特殊情况不能放置皇后
    private boolean isValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false; // 当前列有冲突
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false; // 135°直线无冲突, 行列--
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false; // 45°直线无冲突，行--，列++
            }
        }
        return true;
    }

    private List<String> charToList(char[][] board) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            list.add(new String(board[i]));
        }
        return list;
    }
}
